//归并排序

#include <stdio.h>

#define MAXSIZE 100

void merge(int *list1, int list1_size, int *list2, int list2_size);
void merge_sort(int k[], int n);
void show(int *arr, int len);

int main()
{
    int drr[] = {1, 8, 7, 5, 0};
    //sizeof()它的作用是返回一个对象或类型所占的内存的字节数
    int num = sizeof(drr) / sizeof(drr[0]);
    merge_sort(drr, num);
    show(drr, num);
    return 0;
}

// 递归的方式实现归并排序

// 实现归并，并把结果存放到list1
void merge(int *list1, int list1_size, int *list2, int list2_size)
{
    int i, j, k, m;
    int temp[MAXSIZE];

    i = j = k = 0;

    while (i < list1_size && j < list2_size)
    {
        if (list1[i] < list2[j])
        {
            temp[k] = list1[i];
            k++;
            i++;
        }
        else
        {
            temp[k++] = list2[j++];
        }
    }

    while (i < list1_size)
    {
        temp[k++] = list1[i++];
    }

    while (j < list2_size)
    {
        temp[k++] = list2[j++];
    }

    for (m = 0; m < (list1_size + list2_size); m++)
    {
        list1[m] = temp[m];
    }
}

void merge_sort(int k[], int n)
{
    if (n > 1)
    {
        /*
        *list1是左半部分，list2是右半部分
        */
        int *list1 = k;
        int list1_size = n / 2;
        int *list2 = k + list1_size;
        int list2_size = n - list1_size;

        merge_sort(list1, list1_size);
        merge_sort(list2, list2_size);

        // 把两个合在一起
        merge(list1, list1_size, list2, list2_size);
    }
}

void show(int *arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}